#include <gtest/gtest.h>
#include "common.h"

using namespace ::std;

class Solution {
public:
    int countSubstrings(string s);
};

// 动态规划
// 确定状态数组的形式，保存哪些信息
// 确定状态数组的边界，并初始化动态数组
// 确定状态转移方程
// 可以通过观察暴力法中最耗时的操作来确定要保存哪些信息，看能不能把前面获取的信息有效保存下来，降低后续遍历次数
// dp[i][j]表示区间i到j的字串是否是回文子串
// 优化方向：空间优化，滚动数组，只用一维数组就可以解决？
int Solution::countSubstrings(string s) {
    int size = s.size(), result = 0;
    vector<vector<bool>> dp(size, vector<bool>(size, false));
    for(int i = 0; i < size; ++i) {
        result++; dp[i][i] = true;
        if(i > 0 && s[i] == s[i - 1]) {
            result++;
            dp[i - 1][i] = true;
        }
        for(int j = i - 2; j >= 0; --j) {
            int m = i - 1, n = j + 1;
            if(m < n) break;
            if(dp[n][m] && s[i] == s[j]) {
                result++;
                dp[j][i] = true;
            }
        }
    }
    return result;
}

class CountSubstringsCheck : public ::testing::Test {
public:
	class Solution solution;
};

TEST_F(CountSubstringsCheck, testCountSubstrings_1) {
    string s = "abc";
    EXPECT_TRUE(3 == solution.countSubstrings(s));
}

TEST_F(CountSubstringsCheck, testCountSubstrings_2) {
    string s = "aaa";
    EXPECT_TRUE(6 == solution.countSubstrings(s));
}

TEST_F(CountSubstringsCheck, testCountSubstrings_3) {
    string s = "aksjhdfkjsdhkwersfddsfsdfsdfsdfdssdgdfsfsdfhsdfsfgsabc";
    EXPECT_TRUE(65 == solution.countSubstrings(s));
}

int main() {
	::testing::InitGoogleTest();
	return RUN_ALL_TESTS();
}
